Kruskal method
Algorithm for finding the minimum area tree of an undirected connected graph
O(E log E)
Add the cost of the sides from the cheapest to the least expensive to avoid creating a closed channel.
This closed path can be determined in almost constant time by using [UnionFind
O(E log E) where the edges are sorted by cost.
O(E) if sorted or linear time sort if possible
Minimum Global Tree (Kruskal Method and UnionFind) - Algorithm Workshop
Kruskal Act - Wikipedia
---
This page is auto-translated from /nishio/クラスカル法. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.